Сложеност израчунавања
Важно питање за практичну примену написаних програма је то колико ресурса програм захтева за своје извршавање. Најважнији ресурси су сигурно време потребно за извршавање програма и заузета меморија, мада се могу анализирати и други ресурси (на пример, код мобилних уређаја важан ресурс је утрошена енергија). Дакле, обично се разматрају:
- временска сложеност алгоритма;
- просторна (меморијска) сложеност алгоритма.
На пример, ако један програм израчунава потребан број за 10 секунди, а други за два и по минута, јасно је да је први програм практично примењивији. Међутим, ако први програм за своје извршавање захтева преко 10 гигабајта меморије, други око 1 гигабајт, а ми имамо рачунар са 4 гигабајта меморије, први програм нам је практично неупотребљив (иако ради много брже од другог). Ипак, с обзиром на то да савремени рачунарски системи имају прилично велику количину меморије, време је чешће ограничавајући фактор и у наставку ћемо се чешће бавити анализом временске ефикасности алгоритама.
При том, прилично је релативно колико брзо програм треба да ради да бисмо га сматрали ефикасним. На пример, ако програм успе да за пола сата реши неки нерешен математички проблем, који људи годинама нису могли да реше, он је свакако користан и можемо га сматрати веома ефикасним. Са друге стране, ако програм уграђен у аутомобил контролише кочнице приликом проклизавања, њему и неколико стотина милисекунди израчунавања може бити превише, јер ће за то време аутомобил неконтролисано слетети са пута.
Понашање програма (па и количина утрошених ресурса), наравно, зависи од његових улазних параметара. Јасно је, на пример, да ће програм брже израчунати просечну оцену двадесетак ученика једног одељења, него просечну оцену неколико десетина хиљада ученика који полажу Државну матуру. Такође се може претпоставити да понашање програма не зависи од конкретних оцена које су ученици добили, већ само од броја ученика. Зато сложеност алгоритма често изражавамо у функцији величине (димензије) његових улазних параметара, а не самих вредности параметара. Величина улазне вредности може бити број улазних елемената које треба обрадити, број битова потребних за записивање улаза који треба обрадити, сам улазни број који треба обрадити итд. Увек је потребно експлицитно навести у односу на коју величину улазне вредности се разматра сложеност.
Са друге стране, неки се алгоритми не извршавају исто за све улазе исте величине, па је потребно наћи начин за описивање ефикасности алгоритма на разним могућим улазима исте величине.
Анализа најгорег случаја заснива процену сложености алгоритма на најгорем случају (на случају за који се алгоритам најдуже извршава – у анализи временске сложености, или на случају за који алгоритам користи највише меморије – у анализи просторне сложености). Та процена може да буде варљива, тј. превише песимистична. На пример, ако се програм у 99,9% случајева извршава испод секунде, док се само у 0,1% случајева извршава за око 10 секунди, анализом најгорег случаја закључили бисмо да ће се програм извршавати за око 10 секунди. Са друге стране, анализа најгорег случаја нам даје јаке гаранције да програм који је у најгорем случају довољно ефикасан у свим случајевима може да се изврши са расположивим ресурсима.
У неким ситуацијама могуће је извршити анализу просечног случаја и израчунати просечно време извршавања алгоритма, али да би се то урадило, потребно је прецизно познавати простор допуштених улазних вредности и вероватноћу да се свака допуштена улазна вредност појави на улазу програма. У случајевима када је битна гаранција ефикасности сваког појединачног извршавања програма процена просечног случаја може бити варљива, превише оптимистична, и може да се деси да у неким ситуацијама програм не може да се изврши са расположивим ресурсима. На пример, анализа просечног случаја би за претходни програм пријавила да се у просеку извршава испод једне секунде, међутим, за неке улазе он се може извршавати и преко десет секунди.
Анализа најбољег случаја је, наравно, превише оптимистична и никада нема смисла.
Некада се анализа врши тако да се процени укупно време потребно да се изврши одређен број сродних операција. Тај облик анализе назива се амортизована анализа и у тим ситуацијама нам није битно време извршавања појединачних операција, већ само збирно време извршавања свих операција.
У наставку ће, ако није другачије речено, бити подразумевана анализа најгорег случаја.